//给定一个整数 n ，返回 可表示为两个 n 位整数乘积的 最大回文整数 。因为答案可能非常大，所以返回它对 1337 取余 。 
//
// 
//
// 示例 1: 
//
// 
//输入：n = 2
//输出：987
//解释：99 x 91 = 9009, 9009 % 1337 = 987
// 
//
// 示例 2: 
//
// 
//输入： n = 1
//输出： 9
// 
//
// 
//
// 提示: 
//
// 
// 1 <= n <= 8 
// 
// Related Topics 数学 👍 55 👎 0

package leetcode.editor.cn;

public class _479_LargestPalindromeProduct {
    public static void main(String[] args) {
        Solution solution = new _479_LargestPalindromeProduct().new Solution();
        int n = 5;
        System.out.println(solution.largestPalindrome(n));
    }
    class Solution {
        public int largestPalindrome(int n) {
            if (n == 1) return 9;
            int upper = (int) Math.pow(10, n) - 1;
            int left = upper;
            while (left > 0) {
                long p = left;
                for (int x = left; x > 0; x /= 10) {
                    p = p * 10 + x % 10;
                }

                for(long i = upper; i * i >= p; i--) {
                    if(p % i == 0) {
                        System.out.println(p);
                        return (int) (p % 1337);
                    }
                }
                left--;
            }
            return -1;
        }
        public int largestPalindrome2(int n) {
            if (n == 1) return 9;
            int upper = (int) Math.pow(10, n) - 1;
            int left = upper;
//            left = 99660;
            while (left > 0) {
                long p = left;
                for (int x = left; x > 0; x /= 10) {
                    p = p * 10 + x % 10;
                }

                for(long i = upper; i * i >= p; i--) {
                    if(p % i == 0) {
//                        System.out.println(p);
                        return (int) (p % 1337);
                    }
                }
                left--;
            }
            return -1;
        }
    }

    // 官方题解
    class Solution2 {
        public int largestPalindrome(int n) {
            if (n == 1) return 9;

            int upper = (int) Math.pow(10, n) - 1;
            int ans = 0;
            for (int left = upper; ans == 0; left--) {
                long p = left;
                for (int x = left; x > 0; x /= 10) {
                    p = p * 10 + x % 10;
                }
                for (long x = upper; x * x >= p; --x) {
                    if (p % x == 0) { // x 是 p 的因子
                        ans = (int) (p % 1337);
                        System.out.println(p);
                        break;
                    }
                }
            }
            return ans;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // time out
    class Solution1 {
        public int largestPalindrome(int n) {
            long num = (long) (Math.pow(10, n) * Math.pow(10, n)) - 1;
            while (num > 0) {
                if (isPalindrome(num)) {
                    for (long i = (long) Math.pow(10, n) - 1; i > 0; i--) {
                        if (i * ((long) Math.pow(10, n) - 1) < num) break;
                        if (num / i * i == num) {
                            return (int) (num % 1337);
                        }

                    }
                }
                num--;
            }
            return -1;
        }

        public boolean isPalindrome(long x) {
            if (x < 0 || (x % 10 == 0 && x != 0)) return false;

            long reverseNum = 0;
            while (x > reverseNum) {
                reverseNum = reverseNum * 10 + (x % 10);
                x /= 10;
            }
            return x == reverseNum || x == reverseNum / 10;
        }

        private boolean isPalindrome2(int n) {
            int cur = n;
            int tmp = 0;
            while (cur > 0) {
                tmp = (tmp * 10) + (cur % 10);
                cur /= 10;
            }
            if (tmp == n) return true;
            else return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}